package com.it.zhangjun.arithmetic.DP;

/**
 * @author jun.zhang6
 * @date 2020/10/29
 */
public class _01背包问题 {

    public static int select(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) {
            return 0;
        }
        if (weights == null || weights.length == 0) {
            return 0;
        }
        if (weights.length != values.length) {
            return 0;
        }
        if (capacity <= 0) {
            return 0;
        }
        int[][] dp = new int[values.length + 1][capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
                }
            }
        }
        return dp[values.length][capacity];
    }
}
